Communication systems typically include a plurality of stations connected to one another over a common communication channel. For example, in a community antenna television (CATV) system, a headend is connected by a cable to a plurality of subscriber stations. The cable supports downstream communication from the headend to the subscriber stations and upstream communication from the subscriber stations to the headend. Data, which is transmitted between the headend and the subscriber stations, is transmitted in data frames. Accordingly, when the headend communicates with a subscriber station, the headend transmits in a downstream data frame to the subscriber station, and when a subscriber station communicates with the headend, the subscriber station transmits in an upstream data frame to the headend.
In such a CATV system, the headend and the subscriber stations must share the resources of the cable in some manner. For example, downstream and upstream communications are typically allocated to different frequency ranges. In a sub-split allocation, downstream communications are allocated to a frequency range between 54 MHz and 750 MHz and above, while the upstream communications are allocated to a frequency range below 42 MHz. In a mid-split allocation, downstream communications are allocated to a frequency range of 162 MHz and above, while upstream communications are allocated to a frequency range between 5 to 100 MHz. In a high-split allocation, downstream communications are allocated to a frequency range of 234 MHz and above, while upstream communications are allocated to a frequency range between 5 MHz and 174 MHz.
Moreover, the subscriber stations must also share the resources of the cable in some manner. In a time division multiple access (TDMA) CATV system, the subscriber stations typically share the cable by transmitting data during uniquely assigned and non-overlapping time periods. In a frequency division multiple access (FDMA) CATV system, the subscriber stations share the cable by dividing up the available upstream frequency bandwidth into numerous narrow frequency channels and by allocating to each subscriber station its own corresponding narrow frequency band. In a code division multiple access (CDMA,) CATV system, the subscriber stations share the cable by multiplying their data messages by corresponding assigned code words and then transmitting the result.
A TDMA system, which assigns each subscriber station to a unique time slot, avoids collisions of data transmitted by the subscriber stations but restricts the amount of data throughput from the subscriber stations to the headend. An FDMA system, which allocates to each subscriber station its own corresponding narrow frequency band, similarly restricts throughput because the number of frequency bands allocated to the subscriber stations is limited. A CDMA system likewise limits throughput over a communication cable because the number of code words which are available to be assigned to subscriber stations is limited.
In order to increase throughput of the data transmitted by the subscriber stations to the headend of a CATV system, it is known to divide the upstream data frame, which supports communication from the subscriber stations to the headend, into a number of minislots and data slots. Those subscriber stations, which have data to transmit to the headend, are required to insert a reservation request in a minislot of the current upstream data frame (i.e., the upstream data frame at discrete time n). This reservation request requests the headend to reserve data slots in a subsequent upstream data frame (e.g., the upstream data frame at discrete time n+1) for use by those subscriber stations.
Because the number of minislots in an upstream data frame utilized by such current systems is limited, contention between subscriber stations for access to the is limited number of minislots results in frequent collisions (i.e., contention) between reservation requests. However, it is hoped that at least some reservation requests will be successfully transmitted by subscriber stations to the headend without collision in any given upstream data frame. Therefore, it is generally thought that eventually all subscriber stations will be able to transmit their data to the headend in data slots reserved for that purpose. Yet, because the number of minislots in such systems is limited and fixed, the throughput in such a system is correspondingly limited.
It is also known to increase throughput of the data transmitted by the subscriber stations to the headend of a CATV system by allowing the subscriber stations to contend for the same frequency, time, or code word slots in the upstream data frame and to use a tree algorithm to resolve any resulting collisions. Collisions result when two or more subscriber stations transmit data in the same slot or slots of an upstream data frame. When the headend detects such collisions, the headend initiates a tree algorithm which assigns, for a second layer of contention, a predetermined number of expansion slots in the next upstream data frame for each contention slot in the previous upstream data frame in which there was a collision. In other words, the tree algorithm expands each contention slot in which there was a collision to a predetermined number of expansion slots.
In response to this expansion by the headend, each subscriber station determines whether it transmitted in one of the slots in which there was a collision. Each subscriber station, which determines that it transmitted in a contention slot in which there was a collision, randomly selects in the next upstream data frame one of the expansion slots corresponding to the contention slot of the previous upstream data frame in which it transmitted data. These subscriber stations then re-transmit their data in the corresponding randomly selected expansion slots. If the headend again detects collisions, the tree algorithm assigns, for a third layer of contention, a predetermined number of expansion slots in the next upstream data frame for each slot in the previous upstream data frame in which there was a collision. The contending subscriber stations respond as before. In this way, contention is resolved.
The present invention relates to system which combines the attributes of a protocol which dynamically varies the number of minislots in an upstream data frame, as needed, with the attributes of a dynamic tree algorithm for resolving contention when two or more stations collide in the same slot of an upstream data frame.